package com.example.temp;


import android.os.Build;

import androidx.annotation.RequiresApi;

import java.util.ArrayList;
import java.util.PriorityQueue;

public class Test28 {

    public static void main(String[] args) {

    }

    /**
     * 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
     */


    public class Solution {

        @RequiresApi(api = Build.VERSION_CODES.N)
        public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {

            ArrayList<Integer> arrayList = new ArrayList<>();
            if (k < 1 || input.length < k) {
                return new ArrayList<>();
            }
//            int j = quickSort(input,0,input.length-1);
//
//            if (j==k){
//                arrayList.add()
//                int[] b = Arrays.copyOf(input,j+1);
//            }

            /**
             * PriorityQueue 优先队列  默认升序1234  可以设置为降序4321
             * */
//            PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, new Comparator<Integer>() {
//                        @Override
//                        public int compare(Integer o1, Integer o2) {
//                            return o2-o1;
//                        }
//                    });
            PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);


            for (int i = 0; i < input.length; i++) {
                if (maxHeap.size() < k) {
                    maxHeap.add(input[i]);
                }

                if (maxHeap.size() >= k && maxHeap.peek() > input[i]) {
                    maxHeap.poll();
                    maxHeap.add(input[i]);
                }

            }
            return new ArrayList<>(maxHeap);
        }

        private int quickSort(int[] a, int l, int r) {

            int base = a[l];
            int i = l;
            int j = r;
            while (i < j) {
                while (i < j && a[j] > base)
                    j--;
                while (i < j && a[i] < base)
                    i++;

                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }

            a[l] = a[i];
            a[i] = base;

//            quickSort(a, l, i);
//            quickSort(a, i, j);
            return i;

        }


    }
}
